Natural language is a language spoken or written by humans, as opposed to a programming language or a machine language. A programming language is any artificial language that can be used to define a sequence of instructions that can ultimately be processed and executed by a computer. Defining what is or is not a programming language can be tricky, but general usage implies that the translation process—from the source code which is expressed using the programming language, to the machine code, which is the code that the computer needs to work with—be automated by means of another program, such as a compiler. Both natural languages and programming languages are systematic means of communicating information and instructions from one entity to another, such as man to man or man to machine. Unfortunately, prior programming languages have been an imperfect way of communicating information and instructions from man to machine.
For example, early in the computing era, assembly languages were used to form low-level programming languages. Assembly languages use abbreviations or mnemonic codes in which each statement corresponds to a single machine instruction. Along with the advantage of high efficiency due to direct programmer interaction with system hardware and resources came the undesirable consequence of having to manually update ad hoc organizational schemes, such as data structures, when even slight changes were made to an assembly language program. The high-level languages of today, which provide a level of abstraction above the underlying machine language, evolved from assembly languages. High-level language statements generally use keywords (usually in English) that are translated into more than one machine-language instruction. High-level languages have built-in support for data structures and define a set of syntactic and semantic rules that define the structure of the language. When a slight change is made to a program written in a high-level language, a compiler, which transforms the program into object code by following a predetermined set of syntactic and semantic rules, either reflows the object code as necessary to correspond with the change made to the program or unabashedly informs a programmer of the apparent programming error.
Programmers have leveraged the ability of a compiler to detect errors in the invocation of application programming interfaces (APIs) by checking the signature of an invoking API against the corresponding signature of a defined API. An API is an interface of a program that defines the sort of inputs the program will accept to perform a desired task and the sort of outputs the program will return after the performance of the desired task. APIs allow programs to cooperate together to provide greater functionality than each could provide alone.
An API only specifies what must be provided to the API and what will be returned from the API—not the behaviors of the program underlying the API. For example, to properly cooperate, an “initialization” program must be called before a “do work” program is called, and correspondingly, the “do work” program must be called before a “clean up” program is called. APIs do not capture this ordering idea, or any other ideas that express how programs should cooperate. As a result, like the laborious tasks of maintaining the assembly programs of yesteryear, programmers must once again fit square pegs into round holes by working within the limit of the expressiveness of present high-level languages to ensure that programs correctly cooperate.
The foregoing problem is exacerbated with the proliferation of Web services, which are basically programs located on any number of computing devices interconnected by the Internet. Whereas the specification and the laborious verification of the cooperation of programs within a single computing device can be undertaken—albeit arduously—the task of verifying the intricate ballet associated with the cooperation of multiple Web services (which send multiple messages from multiple computing devices) is an insurmountable problem because of the lack of the expressiveness of present high-level languages. What is needed is a programming language that can express the cooperative dimensions of programs or services, such as ordering and timing, among other things, so that such cooperative dimensions can be programmatically verified.
One partial solution is the use of π-calculus, which is a mathematical language for describing processes in interactive, concurrent systems, such as a system 100 shown in FIG. 1. The system 100 includes a client 102, which is a computer that accesses shared network resources being provided by another computer, such as a server 106, on a local area network or a wide area network, such as the Internet 104. A number of Web services 108, 116 are statically stored as programs on the client 102 and the server 106.
Early operating systems allowed users to run only one program at a time. Users ran a program, waited for it to finish, and then ran another one. Modern operating systems allow users to execute (run) more than one program at a time or even multiple copies of the same program at the same time. A thread is the basic unit used by the operating system to allocate processor time to a program. A thread can include any part of the programming code, including parts currently being executed by another thread. A processor is capable of executing only one thread at a time. However, a multi-tasking operating system, i.e., an operating system that allows users to run multiple programs, appears to execute multiple programs at the same time. In reality, a multi-tasking operating system continually alternates among programs, executing a thread from one program, then a thread from another program, etc. As each thread finishes its sub-task, the processor is given another thread to execute. The extraordinary speed of the processor provides the illusion that all of the threads execute at the same time.
While the terms multi-tasking and multi-processing are sometimes used interchangeably, they have different meanings. Multi-processing requires multi-processors. If a machine has only one processor, the operating system can multi-task, but not multi-process. If a single machine has multiple processors or there are multiple machines (the client 102 and the server 106), each of which has a processor, the operating system of the single machine or the operating systems of multiple machines can both multi-task and multi-process. Both a single machine having multiple processors and multiple machines, each having a processor, define a concurrent system. This is an object of interest for π-calculus.
The core of π-calculus consists of systems of independent, parallel processes (such as Web services 108, 116) that communicate via links (such as a link 124). Links can be any of the following: APIs that become as remote procedure calls; hypertext links that can be created, passed around, and removed; and object references (e.g., “rose”) passed as arguments of method invocations in object-oriented systems. The possibilities of communication for a process with other processes depends on its knowledge of various different links. Links may be restricted so that only certain processes can communicate on them. What sets the π-calculus apart from other process languages is that the scope of a restriction (the context in which a link may be used) may change during execution. For example, when the Web Service 116 sends a restricted name, such as an API previously known only to the Web Service 116, as a message to the Web service 108, which is outside the scope of the restriction, the scope is expanded (or extruded in the mathematic idiom of π-calculus). This means that the scope of the API is enlarged to embrace the Web service 108 receiving the API. In other words, the Web service 108 can now invoke the function represented by the API whereas before the Web service 108 had no knowledge of the API, hence was unable to invoke the API. This procedure allows the communication possibilities of a process to change over time within the framework of π-calculus. A process can learn the names of new links via scope extrusion. Thus a link is a transferable quantity for enhancing communication.
What has been central, foundational, and unchanging about π-calculus is its intense focus on names, such as “rose,” and the passing of names as messages over links. In particular, π-calculus places great emphasis on pure names, each of which is defined to be only a bit pattern. One example of a pure name is the 128-bit space GUID (Globally Unique Identifier) that uniquely identifies an interface or an implementation in the COM component model. Another example of a pure name is a function signature or an API as described above. For additional emphasis, consider the above-discussed problem in this light: suppose there are three APIs (“initialization,” “do work,” and “clean up”) sent to the Web service 108 from the Web service 116, but the Web service 116 must invoke these three APIs only in a particular order (e.g., “initialization” and then “do work” and then “clean up”). While existing a-calculus and its variants allow the three APIs to be sent over the link 124 to reach the Web service 108 from the Web service 116, the existing π-calculus and its variants lack a way for the Web service 116 to express to the Web service 108 the particular order in which the three APIs are to be invoked. In this sense, existing π-calculus and its variants cannot completely express the cooperative dimensions of programs or services, such as ordering and timing, among other things, so that such cooperative dimensions can be programmatically verified.
One Elizabethan poet succinctly provided this adage, metaphorical in form but embodying a timeless observation: “What's in a name? That which we call a rose by any other name would smell as sweet.” This observation made long ago precisely points to a present problem of π-calculus and its variants—a lack of tolerance for the passage of structured data on named links (such as the link 124). In fact, π-calculus unfavorably refers to structured data as “impure names,” which is a negative linguistic construction. Pureness is desirable while impurity is abhorred. Thus impure names in the context of π-calculus are data with some kind of recognizable structure, such as an extensible markup language (XML) document. In practice, it is useful (and at times necessary) for one process to communicate structured data to another process.
Without a flow of data, it is difficult to facilitate communication between processes—except in a very indirect way—to represent mobility or dynamism among processes. To solve this problem, computer scientists have investigated the possibility of allowing processes to flow in communication over links. For example, a process 110 may send to the process 118 a message which represents a third process (not shown). This is known as higher-order π-calculus. Because of the rigidity with which π-calculus handles pure names, instead of sending a process over a link, even higher-order π-calculus variants send a name, which gives access to a desired process, instead of sending the process itself.
Sending a name, rather than a process, can be likened to the traditional programming technique of passing by reference, i.e., passing an address of a parameter from a calling routine to a called routine, which uses the address to retrieve or modify the value of the parameter. The main problem with employing the passing by reference technique in higher-order π-calculus variants is that the technique can inhibit the ability of a concurrent system to become distributed. There are many implementations of π-calculus, namely PICT, Nomadic PICT, TyCO, Oz, and Join, among others. However, these other implementations are either not distributed (PICT) or are not higher-order forms of the π-calculus (Nomadic PICT, TyCo, Oz, and Join).
Thus there is a need for better methods and systems for allowing processes in concurrent, distributed computing networks to interact while avoiding or reducing the foregoing and other problems associated with existing π-calculus and its variants.